package _binary_search;

import java.util.Arrays;

/**
 * 1498. 满足条件的子序列数目
 */
public class Np1498 {
    private final int MOD = (int) (Math.pow(10, 9) + 7);

    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = 0, right = n - 1;
        int ans=0;


        int[] tmp = new int[n];
        tmp[0] = 1;
        for (int i = 1; i < n; i++) {
            tmp[i] = (tmp[i - 1] << 1) % MOD;
        }

        while (left <= right) {
            if (nums[left] + nums[right] > target) right--;
            else {
                ans= (ans + tmp[right - left]) % MOD;
                left++;
            }
        }
        return ans;
    }
}
